AGC017 A Biscuits

公式解説の解法はかなり発想を必要とするので, ここでは別の解法を紹介する.

偶数は和の偶奇に影響しないので奇数を考える. すると, P=0なら奇数は偶数個, P=1なら奇数は奇数個であればよいことがわかる.

よって奇数の個数を全探索し, $ C((全体の奇数の個数), (今見ている奇数の個数)) * 2^(全体の偶数の個数)を計算すればよいことがわかる. 組み合わせの計算はパスカルの三角形を用いるとよい.